1. Field of the Invention
This invention relates generally to non-volatile memory, and more particularly to providing wear leveling using a relative counter in a non-volatile memory system.
2. Description of the Related Art
In general, non-volatile memory is memory that stores data when power is disconnected from the system. Phase-change memory (PCM) and flash memory are examples of non-volatile computer memory in use today. Flash memory is a non-volatile computer memory that can be electrically erased and reprogrammed. Because flash memory retains stored data even when power to the memory is turned off, flash memory is widely used in battery-driven portable devices. For example, flash memory often is utilized in digital audio players, digital cameras, mobile phones, and USB flash drives, which are used for general storage and transfer of data between computers.
Unlike many other storage devices, flash devices cannot be overwritten. Instead, to update data in a particular storage location within flash memory, the location must first be erased, then the new data written in its place. Moreover, when erasing data in a flash device, an entire block must be erased instead of just the particular page or pages of the block that were updated. To facilitate this process, a typical flash controller will find a block of memory that has been previously erased and write the updated page to this new block at the same page offset. Then, the remaining pages of the old block are copied to the new block. Later, the old block is erased and made available for use by some other operation.
However, there are electrical limitations to the number of times a memory block can be erased before the block ceases to function properly. When this occurs, the flash memory system typically experiences a general degradation of overall performance and capacity. The actual wear within a non-volatile memory system depends on how often the individual memory blocks are erased and reprogrammed. For example, if a block is erased repeatedly, that block will wear out relatively quickly. One the other hand, if a block is programmed and the data is allowed to remain for a significant amount of time, the block will wear relatively slowly. Since many prior art non-volatile memory systems search for free blocks starting at the beginning of memory, the erase counts of blocks near the beginning of memory are typically higher than those near the end of memory, as illustrated in FIG. 1.
FIG. 1 is a graph 100 showing the erase counts of a prior art non-volatile memory using a simple search for free blocks when writing data. In FIG. 1, each bar represents the erase counts of each memory block. That is, each bar represents the number of erase-write cycles experienced by each memory block, with longer bars indicating a larger number of erase-write cycles. The memory starts at memory block 0 and ends at memory block N.
When writing data using a simple search for free blocks, the device typically will find the free blocks closest to the location where the search starts. In graph 100, the search starts at memory block 0. Hence, as illustrated in FIG. 1, the memory blocks closest to memory block 0 have higher erase counts than blocks closer to memory block N. When particular blocks cease to function properly because of high wear levels while other blocks are still fully operational, the non-functioning blocks can cause the flash memory system to experience a general degradation of overall performance. Hence, in the example of FIG. 1, the high wear level of memory block 0 can cause the entire memory to be compromised despite the existence of relatively unused blocks near the end of the memory. This can also occur when particular blocks of memory are programmed once and effectively never reprogrammed while other blocks are programmed and erased continuously, as illustrated next in FIG. 2.
FIG. 2 is a graph 200 showing erase counts of a prior art non-volatile memory having low erase-write cycle blocks and high erase-write cycle blocks. Similar to FIG. 1, in FIG. 2 each bar represents the relative wear level of each memory block, with longer bars indicating a larger number of erase-write cycles. The memory starts at memory 0 and ends at memory block N.
In the example of FIG. 2, several low wear level memory blocks 202 are present in the memory. These memory blocks 202 represent memory blocks that have been programmed relatively very few times. For example, they can represent blocks storing a user's favorite songs in an MP3 player. Because the user does not want to remove the songs, the memory blocks 202 storing the song data is programmed once with the song and then not reprogrammed. While the remaining memory blocks 204 are reprogrammed regularly with song data that the user only stores for a relatively short period of time. As a result, the memory blocks 202 storing the favorite songs have a low wear level, while the remaining memory blocks 204 storing transient songs have much higher wear levels. Hence, as in the example of FIG. 1, the high wear level of memory blocks 204 can cause the entire memory to be compromised despite the existence of the low wear level memory blocks 202 storing the favorite song data.
To increase the life of non-volatile memory, wear leveling procedures can be performed on the memory. Wear leveling procedures attempt to utilize the memory in an even fashion, distributing erase-write cycles evenly across the individual memory blocks of the non-volatile memory. One prior art method for wear leveling is to map addresses associated with sectors of worn memory blocks to spare areas once the blocks in which the sectors have been stored have become unusable. Unfortunately, this approach does not effectively distribute erase-write cycles evenly across the individual memory blocks. Moreover, this approach allows the non-volatile memory to degrade as the blocks are remapped.
In view of the foregoing, there is a need for systems and methods for providing effective wear leveling in a non-volatile memory system. The systems and methods should wear blocks evenly allowing increased memory usage. Moreover, the systems and methods should provide effective wear leveling without undue overhead costs and additional memory usage.